1. Field of Invention
The techniques described herein are directed generally to the field of network communications between RBridges.
2. Description of the Related Art
Computer network bridging has great advantages. It provides a plug-and-play environment that is substantially transparent to the network data frames being sent through it. For many applications, no manual configuration of the bridges is needed. Thus in FIG. 1, end stations, such as user client or server computers or Internet Protocol routers can be attached or detached to or from various bridges or multi-access links (such as the multi-access link between Bridge 1 and Bridge 2) and, when attached, will be able to communicate with each other by Ethernet protocols.
Besides Ethernet (IEEE 802.3) links, other types of links can be accommodated by some bridges, such as Wi-Fi (IEEE 802.11), SONET, WiMax (IEEE 802.16), Token Ring, and even virtual links such as IETF PPP (Point-to-Point Protocol). The IEEE (Institute for Electrical and Electronics Engineers) 802.1 Working Group has been the home for bridging standardization.
Thus far bridging standards have been based on the Spanning Tree Protocol (STP). Despite improvements over the years, such as RSTP (Rapid Spanning Tree Protocol) and MSTP (Multiple Spanning Tree Protocol), bridging has continued to be fundamentally based on the insights STP, which are now a quarter of a century old.
Without spanning tree, traffic introduced into the network shown in FIG. 2 would cycle endlessly around the rings formed by Bridges 1, 2, and 5 and by Bridges 2, 3, and 4. STP operates by turning off ports to reduce network connectivity to a loop-free tree structure as shown in FIG. 3 where the port at the Bridge 1 end of the Bridge 1-2 link has been disabled and the Bridge 3 end of the Bridge 3-4 link has been disabled. (MSTP allows several different superimposed trees but this restriction applies to each of them.)
This disabling of ports has the disadvantage of wasting resources. Spanning tree reduces throughput by congesting traffic onto the links that remain connected as part of the tree selected by STP. Further, spanning tree increases the latency (time delay) through the network for most traffic because that traffic does not take the fastest or most direct route through the network but is forced to follow a path within the STP selected tree that typically involves more hops. In FIG. 3, traffic from an end station attached to Bridge 1 to an end station attached to any of Bridges 2 through 4 is forced, by spanning tree, to take an extra hop through Bridge 5.
Other disadvantages of the varieties of STP include slow convergence when there are changes in network components such as the addition, repair, removal or failure of bridges and/or links. The original STP standard defaulted to delays of 30 seconds while even Rapid Spanning Tree Protocol can block traffic for 4 seconds for certain network failures. Such delays can be damaging for applications that require rapid failover, such as real time voice transmission or process control.
VLANs (Virtual Local Area Networks) provide a means of separating Layer 2 end stations into communities such that a bridged network that receives a frame in a particular VLAN will only deliver it to other stations in that same VLAN. The way that STP bridges handle VLANs means that a change in network connectivity leading to a change in the spanning tree can partition VLANs, leaving different stations in the same VLAN disconnected, if bridge ports are not carefully configured.
For further information on some of the above points, see IETF RFC 5556, “Transparent Interconnection of Lots of Links (TRILL): Problem and Applicability Statement,” which is hereby incorporated by reference in its entirety.
RBridges, or Routing Bridges, solve many of the problems of spanning tree protocols by adopting a completely different method. They use link state routing techniques to route on MAC addresses and encapsulate frames with a header including a hop count limit. This idea was presented at and published in the proceedings of the Infocom 2004 meeting under the title “RBridges: Transparent Routing” by Radia Perlman and is described in U.S. Pat. No. 7,398,222, which is hereby incorporated by reference in its entirety.
The Internet Engineering Task Force (IETF) has standardized an RBridge protocol called TRILL (Transparent Interconnection of Lots of Links) based on the IS-IS (Intermediate System to Intermediate System) link state routing protocol. IS-IS has been standardized by ISO (the International Standards Organization) in ISO/IEC 10589:2002, “Intermediate system to Intermediate system routing information exchange protocol for use in conjunction with the Protocol for providing the Connectionless-mode Network Service (ISO 8473),” which is hereby incorporated by reference in its entirety.
Devices that implement the TRILL protocol are called RBridges. We will use the term RBridge below for both the devices and IETF protocol. Just as an area of interconnected physical links and bridges, including at least one bridge, and bounded by end stations, is called a “bridged LAN” (Local Area Network), so an area of links, bridges, and RBridges is called an “RBridge campus”. To bridges, an RBridge appears to be an end station while to end stations, RBridges are as transparent as bridges are.
RBridges do not disable ports to limit traffic to a spanning tree. They provide optimal point-to-point routing of unicast frames through the local area network without configuration. They support multi-pathing of both unicast and multi-destination data that can further increase potential throughput by spreading traffic over alternative paths. They can be incrementally deployed into a bridged LAN by replacing spanning tree bridges with RBridges. Bridged LANs between RBridges appear to those RBridges to be multi-access links. RBridges also provide connectivity between all end stations in each VLAN provided those end stations have connectivity to an RBridge.
When an end station (native) frame, such as that shown in FIG. 4, encounters its first RBridge (the “ingress” RBridge), it is encapsulated with an RBridge header, as shown in FIG. 5, that includes a maximum hop count and has provisions for options. If the frame is to a known unicast address, it is forwarded RBridge hop by RBridge hop to the “egress” RBridge which decapsulates the original native frame and sends it on the link to its end station destination. If the frame is to multiple destinations, it is distributed on a tree and usually decapsulated by multiple egress RBridges that send it on multiple links. RBridges differ from routers in that when a frame is transmitted from a first end station to a second end state, the frame that the first end station transmits is identical to the frame that is ultimately received by the second end station. That is, while RBridges may add headers to transmitted frames, these headers are stripped before the frames are delivered to their end station destinations, such that RBridges do not modify the content that is delivered to the end station. By contrast, routers modify frame data, such that the frame received by an end station is not necessarily identical to the originally transmitted frame.
The RBridge protocol also dynamically allocates 16-bit nicknames for the RBridges in a campus. These nicknames are abbreviations for the RBridge's 48-bit IS-IS System ID. The RBridge Header of an encapsulated frame includes the nickname of the ingress RBridge for that frame and a bit indicating if the frame is single destination (known unicast) or multi-destination (broadcast, multicast, or unknown unicast). There is also an egress nickname field that holds the nickname of the egress RBridge for single destination frames and the root of the distribution tree for multi-destination frames.
Advantages of encapsulation include loop mitigation through use of a hop count field, elimination of the need for original source and destination MAC address learning in transit RBridges, direction of frames towards the egress RBridge (this enables forwarding tables of RBridges to be sized with the number of RBridges rather than the total number of end nodes), and provision of a separate VLAN tag for forwarding traffic between RBridges, independent of the VLAN of the native frame.
Only ingress and egress RBridges need to learn a number of end station MAC addresses proportional to the number of end stations whose traffic they handle. Transit RBridges need only learn addresses proportional to the number of RBridges, which is normally much smaller than the number of end stations. This contrasts with classic IEEE 802.1 bridged networks where all bridges along a path must learn the end station MAC addresses for traffic along that path.